{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Points From Grid Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #union-find #array #two-pointers #matrix #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #并查集 #数组 #双指针 #矩阵 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵查询可获得的最大分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的整数矩阵 <code>grid</code> 和一个大小为 <code>k</code> 的数组 <code>queries</code> 。</p>\n",
    "\n",
    "<p>找出一个大小为 <code>k</code> 的数组 <code>answer</code> ，且满足对于每个整数 <code>queries[i]</code> ，你从矩阵 <strong>左上角</strong> 单元格开始，重复以下过程：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>queries[i]</code> <strong>严格</strong> 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 <code>4</code> 个方向（上、下、左、右）上任一 <strong>相邻</strong> 单元格。</li>\n",
    "\t<li>否则，你不能获得任何分，并且结束这一过程。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在过程结束后，<code>answer[i]</code> 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 <strong>多次</strong> 。</p>\n",
    "\n",
    "<p>返回结果数组 <code>answer</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/19/yetgriddrawio.png\" style=\"width: 571px; height: 151px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]\n",
    "<strong>输出：</strong>[5,8,1]\n",
    "<strong>解释：</strong>上图展示了每个查询中访问并获得分数的单元格。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/20/yetgriddrawio-2.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[5,2,1],[1,1,2]], queries = [3]\n",
    "<strong>输出：</strong>[0]\n",
    "<strong>解释：</strong>无法获得分数，因为左上角单元格的值大于等于 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>4 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>k == queries.length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j], queries[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-points-from-grid-queries](https://leetcode.cn/problems/maximum-number-of-points-from-grid-queries/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-points-from-grid-queries](https://leetcode.cn/problems/maximum-number-of-points-from-grid-queries/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[2,5,7],[3,5,1]]\\n[5,6,2]', '[[5,2,1],[1,1,2]]\\n[3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [0]*len(queries)\n",
    "        idx = sorted(range(len(queries)), key=lambda i: queries[i])\n",
    "        _min = grid[0][0]\n",
    "        level = [(_min, 0, 0)]\n",
    "        grid[0][0] = -1\n",
    "        last = 0\n",
    "        q = deque()\n",
    "        for i in idx:\n",
    "            qv = queries[i]\n",
    "            if _min >= qv:\n",
    "                res[i] = last\n",
    "                continue\n",
    "            top = -1\n",
    "            _min = float('inf')\n",
    "            for pos, t in enumerate(level):\n",
    "                v, r, c = t\n",
    "                if v < qv:\n",
    "                    q.append((r, c))\n",
    "                    if top < 0:\n",
    "                        top = pos\n",
    "                else:\n",
    "                    _min = min(_min, v)\n",
    "                    if top >= 0:\n",
    "                        level[top] = t\n",
    "                        top += 1\n",
    "            if q:\n",
    "                del level[top:]\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                last += 1\n",
    "                for nr, nc in [(r-1, c), (r+1,c), (r, c-1), (r, c+1)]:\n",
    "                    if 0 <= nr < m and 0 <= nc < n:\n",
    "                        v = grid[nr][nc]\n",
    "                        if v < 0: continue\n",
    "                        grid[nr][nc] = -1\n",
    "                        if v < qv:\n",
    "                            q.append((nr, nc))\n",
    "                        else:\n",
    "                            level.append((v, nr, nc))\n",
    "                            _min = min(_min, v)\n",
    "            res[i] = last\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0 \n",
    "        cnt = 0\n",
    "\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0 \n",
    "            ans[qi] = cnt\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 1. 离线查询 + 并查集\n",
    "        # 矩阵元素值从小到达排序，询问也从小到大排序，双指针遍历矩阵元素值和询问，并查集实现相连的过程，同时维护每个连通块的大小\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # mn = m * n\n",
    "\n",
    "        # fa = list(range(mn))\n",
    "        # size = [1] * mn\n",
    "        # def find(x: int) -> int:\n",
    "        #     if fa[x] != x:\n",
    "        #         fa[x] = find(fa[x])\n",
    "        #     return fa[x]\n",
    "        # def merge(from_: int, to: int) -> None:\n",
    "        #     from_ = find(from_)\n",
    "        #     to = find(to)\n",
    "        #     if from_ != to:\n",
    "        #         fa[from_] = to\n",
    "        #         size[to] += size[from_]\n",
    "\n",
    "        \n",
    "        # # 矩阵元素从小到大排序，方便离线\n",
    "        # a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        # ans, j = [0] * len(queries), 0\n",
    "        # # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        # for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "        #     while j < mn and a[j][0] < q:\n",
    "        #         _, x, y = a[j]\n",
    "        #         # 枚举周围四个格子，值小于 q 才可以合并\n",
    "        #         for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "        #             if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "        #                 merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "        #         j += 1\n",
    "        #     if grid[0][0] < q:\n",
    "        #         ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        # return ans\n",
    "                \n",
    "        # 2. 离线查询 + 最小堆\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0  # 充当 vis 数组的作用\n",
    "        cnt = 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0  # 充当 vis 数组的作用\n",
    "            ans[qi] = cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        q = [[grid[0][0], 0, 0]]\n",
    "        grid[0][0] = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        qn = len(queries)\n",
    "        idx = list(range(qn))\n",
    "        idx.sort(key=lambda i: queries[i])\n",
    "        dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "        cnt = 0\n",
    "        ret = [0] * qn\n",
    "        for i in idx:\n",
    "            k = queries[i]\n",
    "            while q and q[0][0] < k:\n",
    "                point, x, y = heappop(q)\n",
    "                cnt += 1\n",
    "                for dx, dy in dirs:\n",
    "                    x2, y2 = x + dx, y + dy\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2]:\n",
    "                        heappush(q, [grid[x2][y2], x2, y2])\n",
    "                        grid[x2][y2] = 0\n",
    "            ret[i] = cnt\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0\n",
    "        cnt = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0\n",
    "            ans[qi] = cnt\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0  # 充当 vis 数组的作用\n",
    "        cnt = 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0  # 充当 vis 数组的作用\n",
    "            ans[qi] = cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0\n",
    "        cnt = 0\n",
    "        for qi, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                val, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                            heappush(h, (grid[x][y], x, y))\n",
    "                            grid[x][y] = 0\n",
    "            ans[qi] = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0  # 充当 vis 数组的作用\n",
    "        cnt = 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0  # 充当 vis 数组的作用\n",
    "            ans[qi] = cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        q = [(x, i) for i, x in enumerate(queries)]\n",
    "        q.sort()\n",
    "        sl = SortedList([(grid[0][0], (0, 0))])\n",
    "        grid[0][0] = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [0] * len(q)\n",
    "        cnt = 0\n",
    "        # print(q)\n",
    "        for a, k in q: \n",
    "            while sl and sl[0][0] < a:\n",
    "                cnt += 1\n",
    "                i, j = sl[0][1]\n",
    "                sl.remove(sl[0])\n",
    "                for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        sl.add((grid[x][y], (x, y)))\n",
    "                        grid[x][y] = 0\n",
    "                # print(sl, sl[0][0], a)\n",
    "                # print(sl and sl[0][0] < x)\n",
    "            ans[k] = cnt\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def next_pos(i, j):\n",
    "            if i > 0:\n",
    "                yield i - 1, j\n",
    "            \n",
    "            if j > 0:\n",
    "                yield i, j - 1\n",
    "\n",
    "            if i < m - 1:\n",
    "                yield i + 1, j\n",
    "            \n",
    "            if j < n - 1:\n",
    "                yield i, j + 1\n",
    "\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        q = [(grid[0][0], 0, 0)]\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[0][0] = grid[0][0]\n",
    "\n",
    "        while q:\n",
    "            x, i, j = heappop(q)\n",
    "\n",
    "            if dist[i][j] < x:\n",
    "                continue\n",
    "            # print(x, i, j, grid[i][j], d)\n",
    "\n",
    "            for a, b in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                if 0 <= a < m and 0 <= b < n:\n",
    "                    xnew = max(x, grid[a][b])\n",
    "\n",
    "                    if xnew < dist[a][b]:\n",
    "                        dist[a][b] = xnew\n",
    "                        heappush(q, (xnew, a, b))\n",
    "\n",
    "        cnt = Counter(dist[i][j] for i in range(m) for j in range(n))\n",
    "\n",
    "        pres_k = list(sorted(cnt.keys()))\n",
    "        pres_v = list(accumulate(cnt[k] for k in pres_k))\n",
    "\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        for i, k in enumerate(queries):\n",
    "            if k > pres_k[0]:\n",
    "                ret[i] = pres_v[bisect.bisect_left(pres_k, k) - 1]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def next_pos(i, j):\n",
    "            if i > 0:\n",
    "                yield i - 1, j\n",
    "            \n",
    "            if j > 0:\n",
    "                yield i, j - 1\n",
    "\n",
    "            if i < m - 1:\n",
    "                yield i + 1, j\n",
    "            \n",
    "            if j < n - 1:\n",
    "                yield i, j + 1\n",
    "\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        q = [(grid[0][0], 0, 0)]\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[0][0] = grid[0][0]\n",
    "\n",
    "        while q:\n",
    "            x, i, j = heappop(q)\n",
    "\n",
    "            if dist[i][j] < x:\n",
    "                continue\n",
    "\n",
    "            for a, b in next_pos(i, j):\n",
    "                xnew = max(x, grid[a][b])\n",
    "\n",
    "                if xnew < dist[a][b]:\n",
    "                    dist[a][b] = xnew\n",
    "                    heappush(q, (xnew, a, b))\n",
    "\n",
    "        cnt = Counter(dist[i][j] for i in range(m) for j in range(n))\n",
    "\n",
    "        pres_k = list(sorted(cnt.keys()))\n",
    "        pres_v = list(accumulate(cnt[k] for k in pres_k))\n",
    "\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        for i, k in enumerate(queries):\n",
    "            if k > pres_k[0]:\n",
    "                ret[i] = pres_v[bisect.bisect_left(pres_k, k) - 1]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        qn = len(queries)\n",
    "        sortedIndex = list(range(qn))\n",
    "        sortedIndex.sort(key=lambda x: queries[x])\n",
    "        ans = [0 for _ in range(qn)]\n",
    "        wl = [(grid[0][0], (0,0))]\n",
    "        cl = collections.deque()\n",
    "        added = [[False for _ in range(n)] for _ in range(m)]\n",
    "        added[0][0] = True\n",
    "        curPoint = 0\n",
    "        for i in range(qn):\n",
    "            qi = sortedIndex[i]\n",
    "            cap = queries[qi]\n",
    "            finished = False\n",
    "            while wl and not finished:\n",
    "                minVal, minIndex = wl[0]\n",
    "                if minVal < cap:\n",
    "                    cl.append(minIndex)\n",
    "                    heapq.heappop(wl)\n",
    "                else:\n",
    "                    finished = True\n",
    "            while cl:\n",
    "                curloc = cl.popleft()\n",
    "                curPoint+=1\n",
    "                for dx, dy in [[-1, 0], [0, -1], [1, 0], [0, 1]]:\n",
    "                    nx, ny = curloc[0]+dx, curloc[1]+dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not added[nx][ny]:\n",
    "                        added[nx][ny] = True\n",
    "                        if grid[nx][ny] < cap:\n",
    "                            cl.append((nx, ny))\n",
    "                        else:\n",
    "                            heapq.heappush(wl, (grid[nx][ny], (nx, ny)))\n",
    "            print(i, curPoint)\n",
    "            ans[qi] = curPoint\n",
    "        return ans\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        k = len(queries)\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        z = []\n",
    "        for i,x in enumerate(queries):\n",
    "            z.append((x,i))\n",
    "        z.sort()\n",
    "        ans = [0] * k\n",
    "        q = PriorityQueue()\n",
    "        q.put((grid[0][0],0,0))\n",
    "        cnt = 0\n",
    "        vis[0][0] = True\n",
    "        for i in range(k):\n",
    "            mx = z[i][0]\n",
    "            while not q.empty() and q.queue[0][0] < mx:           \n",
    "                _,x,y = q.get()\n",
    "                cnt += 1\n",
    "                for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = True\n",
    "                        q.put((grid[nx][ny],nx,ny))\n",
    "            ans[z[i][1]] = cnt\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.maxPoints([[1,2,3],[2,5,7],[3,5,1]],[5,6,2])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        k = len(queries)\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        z = []\n",
    "        for i,x in enumerate(queries):\n",
    "            z.append((x,i))\n",
    "        z.sort()\n",
    "        ans = [0] * k\n",
    "        q = PriorityQueue()\n",
    "        q.put((grid[0][0],0,0))\n",
    "        cnt = 0\n",
    "        vis[0][0] = True\n",
    "        for i in range(k):\n",
    "            mx = z[i][0]\n",
    "            while not q.empty():           \n",
    "                c,x,y = q.get()\n",
    "                if c < mx:\n",
    "                    cnt += 1\n",
    "                    for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                        if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\n",
    "                            vis[nx][ny] = True\n",
    "                            q.put((grid[nx][ny],nx,ny))\n",
    "                else:\n",
    "                    q.put((c,x,y))\n",
    "                    break\n",
    "            ans[z[i][1]] = cnt\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.maxPoints([[1,2,3],[2,5,7],[3,5,1]],[5,6,2])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res, queries, already, heap, score, towards = [0 for _ in range(len(queries))], sorted([queries[i], i] for i in range(len(queries))), [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))], [[grid[0][0], [0, 0]]], 0, [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        already[0][0] = 1\n",
    "        for i in range(len(queries)):\n",
    "            while heap and heap[0][0] < queries[i][0]:\n",
    "                pres = heappop(heap)[1]\n",
    "                score += 1\n",
    "                for x in towards:\n",
    "                    if 0 <= pres[0] + x[0] < len(grid) and 0 <= pres[1] + x[1] < len(grid[0]) and not already[pres[0] + x[0]][pres[1] + x[1]]:\n",
    "                        already[pres[0] + x[0]][pres[1] + x[1]] = 1\n",
    "                        heappush(heap, [grid[pres[0] + x[0]][pres[1] + x[1]], [pres[0] + x[0], pres[1] + x[1]]])\n",
    "            res[queries[i][1]] = score\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        a = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a.append((grid[i][j], i, j))\n",
    "        a.sort()\n",
    "        q = sorted(enumerate(queries), key=lambda x:x[1])\n",
    "        ans = [0] * len(q)\n",
    "        dsu = Dsu(m * n)\n",
    "        j = 0\n",
    "        # print(f'{a}')\n",
    "        for i, x in q:\n",
    "            while j < len(a) and a[j][0] < x:\n",
    "                _, r, c = a[j]\n",
    "                for nr, nc in (r + 1, c),(r - 1, c),(r, c + 1), (r, c - 1):\n",
    "                    if not (0 <= nr < m and 0 <= nc < n): continue\n",
    "                    if grid[nr][nc] < x:\n",
    "                        dsu.merge(r * n + c, nr * n + nc)\n",
    "                j += 1\n",
    "            if grid[0][0] < x:\n",
    "                p = dsu.find(0)\n",
    "                ans[i] = dsu.rk[p] \n",
    "        return ans\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, n):\n",
    "        self.pa = list(range(n))\n",
    "        self.rk = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            self.pa[x] = y\n",
    "            self.rk[y] += self.rk[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        heap = [[grid[0][0], 0]]\n",
    "        visit = set([0])\n",
    "        qr = sorted([(idx, q) for idx, q in enumerate(queries)], key = lambda x: x[1])\n",
    "        res = [0] * len(queries)\n",
    "        cnt = 0\n",
    "        for idx, limit in qr:\n",
    "            while heap and heap[0][0] < limit:\n",
    "                _, coor = heapq.heappop(heap)\n",
    "                cnt += 1 \n",
    "                i, j = coor // n, coor % n \n",
    "                for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                    x = i + d[0]\n",
    "                    y = j + d[1]\n",
    "                    if 0 <= x < m and 0 <= y < n and x * n + y not in visit:\n",
    "                        visit.add(x * n + y)\n",
    "                        heapq.heappush(heap, [grid[x][y], x * n + y])\n",
    "            res[idx] = cnt \n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [0] * len(queries)\n",
    "        qr = sorted([(idx, q) for idx, q in enumerate(queries)], key = lambda x: x[1])\n",
    "        heap = [[grid[0][0], 0]]\n",
    "        visit = set([0])\n",
    "        cnt = 0\n",
    "        for idx, limit in qr:\n",
    "            while heap and heap[0][0] < limit:\n",
    "                cnt += 1 \n",
    "                _, coor = heapq.heappop(heap)\n",
    "                i, j = coor // n, coor % n \n",
    "                for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                    x = i + d[0]\n",
    "                    y = j + d[1]\n",
    "                    if 0 <= x < m and 0 <= y < n and x * n + y not in visit:\n",
    "                        visit.add(x * n + y)\n",
    "                        heapq.heappush(heap, [grid[x][y], x * n + y])\n",
    "            res[idx] = cnt \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, a):\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        if self.find(b) != self.find(a):\n",
    "            self.size[self.find(a)] += self.size[self.find(b)]\n",
    "            self.parent[self.find(b)] = self.find(a)\n",
    "\n",
    "    def getSize(self, a):\n",
    "        return self.size[self.find(a)]\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1])\n",
    "        ans = [0] * len(queries)\n",
    "        vals = []\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                vals.append([grid[i][j], i, j])\n",
    "        vals.sort()\n",
    "        idx = 0\n",
    "        u = UnionFind(n * m)\n",
    "        for i, q in queries:\n",
    "            if grid[0][0] >= q: continue\n",
    "            while idx < len(vals) and vals[idx][0] < q:\n",
    "                x, y = vals[idx][1:]\n",
    "                for dx, dy in pairwise([0, 1, 0, -1, 0]):\n",
    "                    if 0 <= x + dx < n and 0 <= y + dy < m and grid[x + dx][y + dy] < q:\n",
    "                        u.merge(x * m + y, (x + dx) * m + y + dy)\n",
    "                idx += 1\n",
    "            ans[i] = u.getSize(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, a):\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        if self.find(b) != self.find(a):\n",
    "            self.size[self.find(a)] += self.size[self.find(b)]\n",
    "            self.parent[self.find(b)] = self.find(a)\n",
    "\n",
    "    def getSize(self, a):\n",
    "        return self.size[self.find(a)]\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1])\n",
    "        ans = [0] * len(queries)\n",
    "        vals = []\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                vals.append([grid[i][j], i, j])\n",
    "        vals.sort()\n",
    "        idx = 0\n",
    "        u = UnionFind(n * m)\n",
    "        for i, q in queries:\n",
    "            if grid[0][0] >= q: continue\n",
    "            while idx < len(vals) and vals[idx][0] < q:\n",
    "                x, y = vals[idx][1:]\n",
    "                for dx, dy in pairwise([0, 1, 0, -1, 0]):\n",
    "                    if 0 <= x + dx < n and 0 <= y + dy < m and grid[x + dx][y + dy] < q:\n",
    "                        u.merge(x * m + y, (x + dx) * m + y + dy)\n",
    "                idx += 1\n",
    "            ans[i] = u.getSize(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "        fa = list(range(mn))\n",
    "        size = [1]  * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int)->None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[to] =from_\n",
    "                size[from_] += size[to]\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "返回每次查询获得的分数 --> 连通块的大小\n",
    "离线查询+并查集\n",
    "合并的方向就定为从小到大合并\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mn=m*n\n",
    "        fa=list(range(mn))\n",
    "        sz=[1]*mn\n",
    "        def find(x:int)->int:\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        #怎么对整个矩阵排序呢？\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        #找到所有小于q[i]的单元格位置\n",
    "        ans=[0]*len(queries)\n",
    "        j=0\n",
    "        for i,q in sorted(enumerate(queries),key=lambda z:z[1]):\n",
    "            while j<mn and a[j][0]<q:\n",
    "                x,y=a[j][1],a[j][2]\n",
    "                for x2,y2 in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=x2<m and 0<=y2<n and a[j][0]>=grid[x2][y2]:\n",
    "                        #将(x2,y2)向(x,y)合并\n",
    "                        fx=find(x*n+y)\n",
    "                        fy=find(x2*n+y2)\n",
    "                        if fx==fy:\n",
    "                            continue\n",
    "                        fa[fy]=fx\n",
    "                        sz[fx]+=sz[fy]\n",
    "                j+=1\n",
    "            if grid[0][0]>=q:ans[i]=0\n",
    "            else:ans[i]=sz[find(0)]\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        a = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a.append((grid[i][j], i, j))\n",
    "        a.sort()\n",
    "        q = sorted(enumerate(queries), key=lambda x:x[1])\n",
    "        ans = [0] * len(q)\n",
    "        dsu = Dsu(m * n)\n",
    "        j = 0\n",
    "        print(f'{a}')\n",
    "        for i, x in q:\n",
    "            while j < len(a) and a[j][0] < x:\n",
    "                _, r, c = a[j]\n",
    "                for nr, nc in (r + 1, c),(r - 1, c),(r, c + 1), (r, c - 1):\n",
    "                    if not (0 <= nr < m and 0 <= nc < n): continue\n",
    "                    if grid[nr][nc] < x:\n",
    "                        dsu.merge(r * n + c, nr * n + nc)\n",
    "                j += 1\n",
    "            if grid[0][0] < x:\n",
    "                p = dsu.find(0)\n",
    "                ans[i] = dsu.rk[p] \n",
    "        return ans\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, n):\n",
    "        self.pa = list(range(n))\n",
    "        self.rk = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            self.pa[x] = y\n",
    "            self.rk[y] += self.rk[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        now = 0\n",
    "        ans = 0\n",
    "        heap = [(grid[0][0], 0, 0)]\n",
    "        seen = set([(0, 0)])\n",
    "        q = []\n",
    "        while heap:\n",
    "            now = heap[0][0] + 1\n",
    "            while heap and heap[0][0] < now:\n",
    "                nex, x, y = heappop(heap)\n",
    "                ans += 1\n",
    "                for a, b in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                    if 0 <= a < m and 0 <= b < n and (a, b) not in seen:\n",
    "                        seen.add((a, b))\n",
    "                        heappush(heap, (grid[a][b], a, b))\n",
    "            q.append((now, ans))\n",
    "        res = [0]*len(queries)\n",
    "        for i, k in enumerate(queries):\n",
    "            where = bisect_right(q, (k, inf))\n",
    "            if where:\n",
    "                res[i] = q[where-1][-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "练习一下并查集\n",
    "离线查询，并查集合并方向->小分数向大分数合并，由于不能按秩合并，最坏情况是（在均摊计算下）NlogN\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        #并查集模板\n",
    "        #首先是对下标写并查集\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        mn=m*n\n",
    "        fa=list(range(mn))\n",
    "        size=[1]*(mn) #维护并查集内的元素个数，返回答案\n",
    "        def find(x:int)->int:\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def merge(from_:int,to:int)->None:\n",
    "            from_=find(from_)\n",
    "            to=find(to)\n",
    "            if from_!=to:\n",
    "                fa[from_]=to\n",
    "                size[to]+=size[from_]\n",
    "\n",
    "        #以后绑定下标都这么写\n",
    "        #巧妙的做法是，将矩阵元素从小到大排序，然后一边遍历，一边计算\n",
    "        a=sorted((x,i,j) for i,row in enumerate(grid) for j,x in enumerate(row))\n",
    "\n",
    "        ans,j=[0]*len(queries),0\n",
    "        for idx,q in sorted(enumerate(queries),key=lambda z:z[1]):\n",
    "            while j<mn and a[j][0]<q:\n",
    "                _,x,y=a[j]\n",
    "                for x2,y2 in (x+1,y),(x-1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=x2<m and 0<=y2<n and grid[x2][y2]<q:\n",
    "                        merge(x*n+y,x2*n+y2)\n",
    "                j+=1\n",
    "            if grid[0][0]<q:\n",
    "                ans[idx]=size[find(0)]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # mn = m * n\n",
    "\n",
    "        # fa = list(range(mn))\n",
    "        # size = [1] * mn\n",
    "\n",
    "        # def find(node):\n",
    "        #     if fa[node] != node:\n",
    "        #         fa[node] = find(fa[node])\n",
    "        #     return fa[node]\n",
    "\n",
    "        # def union(from_, to_):\n",
    "        #     x, y = find(from_), find(to_)\n",
    "\n",
    "        #     if x != y:\n",
    "        #         fa[x] = y\n",
    "        #         size[y] += size[x]\n",
    "\n",
    "        # record = []\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         record.append((grid[i][j], i, j))\n",
    "        # record.sort()\n",
    "\n",
    "        # queries_sort = [(i, q) for i, q in enumerate(queries)]\n",
    "        # queries_sort = sorted(queries_sort, key=lambda k: k[1])\n",
    "\n",
    "        # res = [0] * len(queries)\n",
    "\n",
    "        # for index, q in queries_sort:\n",
    "        #     cur = 0\n",
    "        #     while cur < mn and record[cur][0] < q:\n",
    "        #         _, x, y = record[cur]\n",
    "        #         for x_, y_ in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "        #             if 0 <= x_ < m and 0 <= y_ < n and grid[x_][y_] < q:\n",
    "        #                 union(x*n+y, x_*n+y_)\n",
    "        #         cur += 1\n",
    "\n",
    "        #     if grid[0][0] < q:\n",
    "        #         res[index] = size[find(0)]\n",
    "        # return res\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "        fa = list(range(mn))\n",
    "        size = [1]  * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int)->None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(from_, to):\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key=lambda x: x[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 1. 离线查询 + 并查集\n",
    "        # 矩阵元素值从小到达排序，询问也从小到大排序，双指针遍历矩阵元素值和询问，并查集实现相连的过程，同时维护每个连通块的大小\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        \n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "        a = []\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                a.append((x, i, j))\n",
    "        a.sort()\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda q: q[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集初始化\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询从小到大排序\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        mn = m * n\n",
    "\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "\n",
    "        def find(node):\n",
    "            if fa[node] != node:\n",
    "                fa[node] = find(fa[node])\n",
    "            return fa[node]\n",
    "\n",
    "        def union(from_, to_):\n",
    "            x, y = find(from_), find(to_)\n",
    "\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "                size[y] += size[x]\n",
    "\n",
    "        record = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                record.append((grid[i][j], i, j))\n",
    "        record.sort()\n",
    "\n",
    "        queries_sort = [(i, q) for i, q in enumerate(queries)]\n",
    "        queries_sort = sorted(queries_sort, key=lambda k: k[1])\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        cur = 0\n",
    "        for index, q in queries_sort:\n",
    "            while cur < mn and record[cur][0] < q:\n",
    "                _, x, y = record[cur]\n",
    "                for x_, y_ in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                    if 0 <= x_ < m and 0 <= y_ < n and grid[x_][y_] < q:\n",
    "                        union(x*n+y, x_*n+y_)\n",
    "                cur += 1\n",
    "\n",
    "            if grid[0][0] < q:\n",
    "                res[index] = size[find(0)]\n",
    "        return res\n",
    "\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_, to):\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = fa[to]\n",
    "                size[to] += size[from_]\n",
    "        a = sorted((x, i, j)for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda x:x[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x1, y1 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x1 < m and 0 <= y1 < n and grid[x1][y1]  < q:\n",
    "                        merge(x * n + y, x1 * n + y1)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        vis = {(0, 0)}\n",
    "        cnt = 0\n",
    "        q = [(grid[0][0], 0, 0)]\n",
    "        for num, idx in sorted(zip(queries, list(range(len(queries))))):\n",
    "            \n",
    "            while q and q[0][0] < num:\n",
    "                _, x, y = heapq.heappop(q)\n",
    "                cnt += 1\n",
    "                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis:\n",
    "                        vis.add((nx, ny))\n",
    "                        heapq.heappush(q, (grid[nx][ny], nx, ny))\n",
    "\n",
    "            ans[idx] = cnt\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k=len(queries)\n",
    "        \n",
    "        queries=[(queries[i],i) for i in range(k)]\n",
    "        queries.sort()\n",
    "        \n",
    "        count=0\n",
    "        q=[(grid[0][0],0,0)]\n",
    "        \n",
    "        \n",
    "        ans=[0]*k\n",
    "        \n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        visited=set()\n",
    "        visited.add((0,0))\n",
    "        for e in range(k):\n",
    "            \n",
    "            while q and q[0][0]<queries[e][0]:\n",
    "                count+=1\n",
    "                _,i,j=heappop(q)\n",
    "                \n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=i+ii,j+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and (newi,newj) not in visited:\n",
    "                        heappush(q,(grid[newi][newj],newi,newj))\n",
    "                        visited.add((newi,newj))\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "            ans[queries[e][1]]=count\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], qu: List[int]) -> List[int]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k=len(qu)\n",
    "        ans=[0]*k\n",
    "        \n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        \n",
    "        for i in range(k):\n",
    "            qu[i]=(qu[i],i)\n",
    "        qu.sort()\n",
    "        \n",
    "        count=0\n",
    "        q=[(grid[0][0],0,0)]\n",
    "        visited=set()\n",
    "        visited.add((0,0))\n",
    "        \n",
    "        for thisq,index in qu:\n",
    "            \n",
    "            while q and q[0][0]<thisq:\n",
    "                count+=1\n",
    "                _,i,j=heappop(q)\n",
    "                \n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=i+ii,j+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and (newi,newj) not in visited:\n",
    "                        visited.add((newi,newj))\n",
    "                        heappush(q,(grid[newi][newj],newi,newj))\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            ans[index]=count\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
